import java.util.PriorityQueue;

//数据流的中位数
//https://leetcode.cn/problems/find-median-from-data-stream/
public class Test {

}

class MedianFinder
{
    PriorityQueue<Integer> left;
    PriorityQueue<Integer> right;
    public MedianFinder()
    {
        left = new PriorityQueue<Integer>((a, b) -> b - a); // ⼤根堆
        right = new PriorityQueue<Integer>((a, b) -> a - b); // ⼩根堆
    }

    public void addNum(int num)
    {
        // 分情况讨论
        if(left.size() == right.size())
        {
            if(left.isEmpty() || num <= left.peek())
            {
                left.offer(num);
            }
            else
            {
                right.offer(num);
                left.offer(right.poll());
            }
        }
        else
        {
            if(num <= left.peek())
            {
                left.offer(num);
                right.offer(left.poll());
            }
            else
            {
                right.offer(num);
            }
        }
    }

    public double findMedian()
    {
        if(left.size() == right.size()) return (left.peek() + right.peek()) /
                2.0;
        else return left.peek();
    }
}
